/**
 * @see https://www.bilibili.com/video/BV18x411V7fm?from=search&seid=8495344017789972615
 */
// 一共有多少个工作选择
var n = 8;
// 可工作的时间段
var time = [[1, 4], [3, 5], [0, 6], [4, 7], [3, 8], [5, 9], [6, 10], [8, 11]];
var start = [1, 3, 0, 4, 3, 5, 6, 8];
var end = [4, 5, 6, 7, 8, 9, 10, 11];
// 每个时间段的收益
var money = [5, 1, 8, 4, 6, 3, 2, 4];

// 选择对应位置任务时，前面还可以选择的任务号
let prev = [];
// 任务对应可获得的奖励
let opts = [];
let tasks = [];
// 先计算
for (let index = 0; index < n; index++) {
  const sx = start[index];
  let lessItems = getPrevMax(sx);
  prev[index] = lessItems.length === 0 ? 0 : Number(lessItems[0]);
}

function getMatchItems(ln) {
  // 在选择与不选择中匹配
  for (let index = 0; index < n; index++) {
    let range = [];
    // 完成当前任务可以获取的奖励
    const value = money[index];
    // 当仅完成第index个任务时，还可以在前面挑选的任务
    const preValue = prev[index];
    let left = opts[index - 1];
    let right = (preValue === 0 ? 0 : opts[preValue - 1]) + value;
    let chose = index <= 0 ? value : Math.max(left, right);
    // 选择当前任务的最大收益
    opts[index] = chose;
    // 计算对应的任务列表，利用每一个选择，选择左边，选择右边分别对应下面三个if - else if - else
    // opts[i] 表示最多任务数为i时的最大收益
    // prev[i] 表示做任务i前，前面还可以做的任务号，将任务i和前面可选任务号的价值相加，即可得出做任务i时的opts[i]的最大收益
    // 动态规划，当一定要做某个任务时的选择，如果只有3个任务，那么选择就是在前面的任务里选择和在前一个任务里选择，前面已经
    // 计算过了，任务3的前面可选择任务数为0，则下面二叉树里的右边prev[i] = 0，0 + v3，如果prev[i]不等于0，则将已经计算过的opts[prev[i]]的价值相加
    /**
     *      opts[i]
     *      /     \
     *     /       \
     * opts[i-1]  opts[prev[i]] + vi(当前任务的价值)
     */
    if(index === 0) {
      tasks.push([index + 1])
    } else if(left < right) { // 选择右边，则找出右边对应的选择
      tasks.push(preValue === 0 ? [index + 1] : tasks[preValue - 1].concat(index + 1));
    } else {
      tasks.push(tasks[index - 1]);
    }
  }
}
/**
 * opts[6] = {opts[5, opts[2] + 3]}
 * opts[5] = {opts[4], 0 +}
 */
getMatchItems();
console.log(opts)
console.log(tasks)
console.log(prev);

// 结束值比另外一个任务的起始值要小
function getPrevMax(val) {
  let index = {};
  end.filter((item, i) => {
    if(item <= val) {
      index[i + 1] = val;
      return true;
    }
    return false;
  });
  console.log(index)
  // 计算离它最近的一个，倒序排序
  return Object.keys(index).sort().reverse();
}